// 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点
#include <iostream>
using namespace std;
enum Color
{
    red,
    black
};
template <class T>
struct RBTreeNode
{
    RBTreeNode(const T& data = T())
        : _left(nullptr)
        , _right(nullptr)
        , _parent(nullptr)
        , _data(data)
        , _color(red)
    {}
    RBTreeNode<T>* _left;
    RBTreeNode<T>* _right;
    RBTreeNode<T*> _parent;
    T _data;
    Color _color;
};
template<class T>
class RBTree
{
    typedef RBTreeNode<T> Node;
public:
    RBTree()
    {
        _pHead = new Node;
        _pHead->_pLeft = _pHead;
        _pHead->_pRight = _pHead;
    }

    // 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
    // 注意：为了简单起见，本次实现红黑树不存储重复性元素
    bool Insert(const T& data)
    {
        //没有根结点
        Node* root = _pHead->_parent;
        if(root == nullptr)
        {
            root = new Node(data);
            root->_parent = _pHead;
            root->_color = black;
        }
        //有根结点
        else
        {
            Node* cur = root;
            Node* parent = root;
            while(cur)
            {
                if(cur->_data > data)
                {
                    parent = cur;
                    cur = cur->_left;
                }
                else if(cur->_data < data)
                {
                    parent = cur;
                    cur = cur->_right;
                }
                else
                {
                    return false;
                }
            }

            Node* newnode = new Node(data);
            if(parent->_data > data)
            {
                parent->_left = newnode;
            }
            else
            {
                parent->_right = newnode;
            }
            newnode->_parent = parent;

            //判断颜色
            AssertColor(parent, newnode);
        }

        //更新最左节点
        _pHead->_left = LeftMost();
        //更新最右节点
        _pHead->_right = RightMost();
        return true;
    }

    // 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
    Node* Find(const T& data)
    {
        Node* cur = GetRoot();
        while(cur)
        {
            if(cur->_data > data)
            {
                cur = cur->_left;
            }
            else if(cur->_data < data)
            {
                cur = cur->_right;
            }
            else
            {
                return cur;
            }
        }
        return nullptr;
    }


    // 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
    bool IsValidRBTRee()
    {

    }
private:
    //判断颜色
    void AssertColor(const Node*& parent, const Node*& cur)
    {
        while(cur != _pHead->_parent)
        {
            //父亲是黑色节点，不会影响树的性质
            if(parent->_color == black)
            {
                return;
            }
            //父亲为红色节点，需要改变颜色
            else
            {
                Node* g_parent = parent->_parent;
                Node* uncle = g_parent->_left == parent ? g_parent->_right : g_parent->_left;
                //叔叔存在且为红
                if(uncle && uncle->_color == red)
                {
                    parent->_color = uncle->_color = black;
                    g_parent->_color = red;
                    cur = g_parent;
                    parent = cur->_parent;
                }
                    //叔叔存在且为黑 || 叔叔不存在
                else
                {

                }
            }
        }

        _pHead->_parent = black;
    }

    bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack)
    {

    }
    // 左单旋
    void RotateL(Node* pParent)
    {

    }
    // 右单旋
    void RotateR(Node* pParent)
    {

    }
    // 为了操作树简单起见：获取根节点
    Node*& GetRoot()
    {
        return _pHead->_parent;
    }
    // 获取红黑树最左侧节点
    Node* LeftMost()
    {
        Node* cur = _pHead->_parent;
        while(cur->_left)
        {
            cur = cur->_left;
        }
        return cur;
    }

    // 获取红黑树最右侧节点
    Node* RightMost()
    {
        Node* cur = _pHead->_parent;
        while(cur->_right)
        {
            cur = cur->_right;
        }
        return cur;
    }
private:
    Node* _pHead;
};